package com.topInterview;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: huangzhigao
 * @Date: 2022/2/13 17:57
 */
public class Leecode17_telephone {
    public static char[][] chars = {
            {'a', 'b', 'c'},
            {'d', 'e', 'f'},
            {'g', 'h', 'i'},
            {'j', 'k', 'l'},
            {'m', 'n', 'o'},
            {'p', 'q', 'r', 's'},
            {'t', 'u', 'v'},
            {'w', 'x', 'y', 'z'}
    };

    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return new ArrayList();
        }
        List<String> ans = new ArrayList<>();
        char[] ss = digits.toCharArray();
        //path去存每次选择的字符，整个path最长为digits的长度
        char[] path = new char[ss.length];
        process(ss, 0, path, ans);
        return ans;
    }


    public void process(char[] ss, int index, char[] path, List<String> ans) {
        if (index == ss.length) {
            ans.add(String.valueOf(path));
        } else {
            //按键2对应的是chars的0行
            int i = ss[index] - '2';
            char[] aChar = chars[i];
            for (char c : aChar) {
                path[index] = c;
                process(ss, index + 1, path, ans);
            }
        }
    }
}


